#include <stdio.h>
#include <stdlib.h>

typedef int ElemSet; /* 默认元素为整数*/
#define kMinRun 4
#define Swap(x, y) { ElemSet t = x; x = y; y = t; }

typedef struct RunNode *Runs;
struct RunNode {
    int start; /* 有序段在a中的起始下标 */
    int len; /* 有序段长度 */
};

/* 堆栈定义及操作 */
typedef enum {false, true} bool;
typedef Runs SElemSet;
#define NIL NULL
typedef struct StackNode *Position; /* 指针即结点位置 */
struct StackNode {
    SElemSet data; /* 存储数据 */
    Position next; /* 链式栈中下一个元素的位置 */
};
typedef struct StackHeadNode *Stack;
struct StackHeadNode {
    int size; /* 链式栈中当前元素个数 */
    Position top; /* 链式栈的栈顶指针，初始化为NULL */
};

void InitStack(Stack stack);
bool IsEmpty(Stack stack);
void Push(Stack stack, SElemSet x);
SElemSet Top(Stack stack);
SElemSet Peek(Stack stack, int k);
void Pop(Stack stack);
void DestroyStack(Stack stack);
/* 堆栈定义及操作结束 */

void Reverse(ElemSet *a, int l, int r);
Runs GetRun(ElemSet *a, int l, int r);
void TwoWayMerge(ElemSet *a, int l, int m, int r);
void Merge(ElemSet *a, Stack stack);

/* 算法10-22：蒂姆排序 TimSort(a,l,r) */
void TimSort(ElemSet *a, int l, int r) {
    int n, p;
    Stack stack;
    Runs run, s1, s2, s3, s4;

    stack = (Stack)malloc(sizeof(struct StackHeadNode));
    InitStack(stack);
    p = l; /* 初始化有序段的起始位置 */
    while (p <= r) {
        run = GetRun(a, p, r); /* 获取一个有序段 */
        Push(stack, run); /* 存入栈中 */
        p += run->len; /* 下一个有序段的起始位置 */
        while (stack->size > 1) { /* 检查栈中元素。此时至少有2个元素 */
            s1 = Peek(stack, 1);
            s2 = Peek(stack, 2);
            if (stack->size == 2) { /* 只有2个段*/
                if (s1->len > s2->len) { /* 需要归并 */
                    Merge(a, stack); /* s2与s1归并 */
                } else { /* 不需要归并 */
                    break;
                }
            } else { /* 至少3个段 */
                s3 = Peek(stack, 3);
                if (s2->len <= s1->len || s3->len <= (s1->len + s2->len)) { /* 需要归并 */
                    if (s1->len <= s3->len) { /* s2与s1归并 */
                        Merge(a, stack);
                    } else { /* s2与s3归并 */
                        s1 = Top(stack);
                        Pop(stack); /* 先弹出s1 */
                        Merge(a, stack); /* s2与s3归并 */
                        Push(stack, s1); /* 恢复s1在栈中的位置 */
                        if (stack->size > 3) { /* 归并可能引起 s2,s3,s4不满足约束 */
                            s2 = Peek(stack, 2);
                            s3 = Peek(stack, 3);
                            s4 = Peek(stack, 4);
                            if (s4->len <= (s3->len + s2->len)) { /* s2与s1归并 */
                                Merge(a, stack);
                            }
                        }
                    }
                } else { /* 不需要归并 */
                    break;
                }
            }
        }
    }
    while (stack->size > 1) {
        Merge(a, stack);
    }
    DestroyStack(stack);
}
/* 算法10-22 结束 */

int main(void) {
    ElemSet *a; /* 数组a的下标从0开始 */
    int n, i;

    scanf("%d", &n);
    a = (ElemSet *)malloc(sizeof(ElemSet) * n);
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    TimSort(a, 0, n - 1);
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }

    return 0;
}

/* 堆栈操作 */
void InitStack(Stack stack) {
    /* 初始化一个空的链式栈 */
    stack->size = 0;
    stack->top = NULL;
}

bool IsEmpty(Stack stack) {
    /* 判断栈是否为空 */
    if (stack->size == 0)
        return true;
    else
        return false;
}

void Push(Stack stack, SElemSet x) {
    Position new_node;

    new_node = (Position)malloc(sizeof(struct StackNode));
    new_node->data = x;
    new_node->next = stack->top;
    stack->top = new_node;
    stack->size++;
}

SElemSet Top(Stack stack) {
    if (IsEmpty(stack)) {
        printf("错误：栈为空。\n");
        return NIL;
    } else {
        return stack->top->data;
    }
}

SElemSet Peek(Stack stack, int k) {
    /* 返回栈顶开始第k个元素的值 */
    Position p;
    int i;

    p = stack->top;
    for (i = 1; i < k; i++) {
        if (p == NULL) {
            break;
        } else {
            p = p->next;
        }
    }
    if (i < k) {
        printf("错误：不存在第%d个元素。\n", k);
        return NIL;
    } else {
        return p->data;
    }
}

void Pop(Stack stack) {
    Position temp;

    if (IsEmpty(stack)) {
        printf("错误：栈为空。\n");
    } else {
        temp = stack->top;
        stack->top = stack->top->next;
        free(temp);
        stack->size--;
    }
}

void DestroyStack(Stack stack) {
    free(stack);
}
/* 堆栈操作结束 */

void Reverse(ElemSet *a, int l, int r) {
    int i, j;

    for (i = l, j = r; i < j; i++, j--) {
        Swap(a[i], a[j]);
    }
}

Runs GetRun(ElemSet *a, int l, int r) {
    /* 从a[l]开始找长度不小于kMinRun的非递减段，并返回段长度 */
    bool is_dec;
    int i, j;
    ElemSet t;
    Runs run;

    run = (Runs)malloc(sizeof(struct RunNode));
    run->start = l;
    if (l == r) {
        run->len = 1;
    } else {
        is_dec = (a[l] > a[l + 1]); /* 是否严格递减 */
        for (i = l + 1; i <= r; i++) {
            if ((is_dec == true && a[i] >= a[i - 1]) || (is_dec == false
                    && a[i] < a[i - 1])) {
                break;
            }
        }
        if (is_dec == true) {
            Reverse(a, l, i - 1);
        }
        while (i <= r && (i - l) < kMinRun) {
            t = a[i];
            for (j = i; j >= (l + 1); j--) {
                if (a[j - 1] > t) {
                    a[j] = a[j - 1];
                } else {
                    break;
                }
            }
            a[j] = t;
            i++;
        }
        run->len = i - l;
    }
    return run;
}

void TwoWayMerge(ElemSet *a, int l, int m, int r) {
    int i, j, k;
    ElemSet *t;

    t = (ElemSet *)malloc(sizeof(ElemSet) * (r - l + 1)); /* 创建临时数组 */
    i = l;
    j = m + 1;
    k = 0;
    while (i <= m || j <= r) {
        if (j > r || (i <= m && a[i] <= a[j])) {
            t[k] = a[i]; /* 将a[i]添加至t末尾 */
            i++;
        } else {
            t[k] = a[j]; /* 将a[j]添加至t末尾 */
            j++;
        }
        k++;
    }
    for (i = l; i <= r; i++) { /* 将归并后的有序序列t复制回a中 */
        a[i] = t[i - l];
    }
}

void Merge(ElemSet *a, Stack stack) {
    /* 将栈顶两个段弹出进行归并，并将结果压回栈顶 */
    Runs s1, s2;

    s1 = Top(stack);
    Pop(stack);
    s2 = Top(stack);
    Pop(stack);
    TwoWayMerge(a, s2->start, s1->start - 1, s1->start + s1->len - 1);
    s2->len += s1->len;
    Push(stack, s2);
}